package _11_整理题目._3_字符串_递归_dfs_bfs_双指针._子串子序列_最值;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 *
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * 注意 子串是连续的，子序列是非连续的
 *
 * 思路：使用队列，或者双指针
 *
 */
public class _011_最长无重复子串 {

    // 返回长度
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Queue<Character> queue = new LinkedList<>();
        int max = 0;
        String ans = "";
        for(int i=0; i<n; i++) {
            while(queue.contains(s.charAt(i))) {
                queue.poll();
            }
            queue.offer(s.charAt(i));
            max = Math.max(max, queue.size());
        }
        return max;
    }

    @Test
    public void main() {
        String s = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(s));
        System.out.println(lengthOfLongestSubstring1(s));
    }

    // 返回子串
    public String lengthOfLongestSubstring1(String s) {
        int n = s.length();
        Queue<Character> queue = new LinkedList<>();
        int max = 0;
        String ans = "";
        for(int i=0; i<n; i++) {
            while(queue.contains(s.charAt(i))) {
                queue.poll();
            }
            queue.offer(s.charAt(i));
            if (queue.size() > max) {
                Character[] characters = queue.toArray(new Character[queue.size()]);
                String tmp = "";
                for (Character character : characters) {
                    tmp += character;
                }
                ans = tmp;
                max = queue.size();
            }
        }
        return ans;
    }
}
